package code;

public class Code61 {
	
	public ListNode reverse(ListNode head){
		
		ListNode p,q,pre;
		pre=null;
		q=null;
		p=head;
		while(p!=null){
			pre=q;
			q=p;
			p=p.next;
			if(pre!=null){
				q.next=pre;
			}
		}
		if(head.next!=null)
		    head.next=null;
		if(pre!=null)
			q.next=pre;
		return q;
	}
	
    public ListNode rotateRight(ListNode head, int k) {
    	if(head==null || k==0 || head.next==null)
    		return head;
    	int size=0;
    	ListNode p,q,tail,rec;
    	p=head;
    	while(p!=null){
    		size++;
    		p=p.next;
    	}
    	k%=size;
    	tail=reverse(head);
    	p=tail;
    	while(p!=null && k-->1){
//    		System.out.println(p.val);
    		p=p.next;
    	}
    	
//    	System.out.println("-----"+p.val);
    	q=p.next;
    	p.next=null;
    	head=reverse(tail);
    	p=reverse(q);
    	tail.next=p;
    	
    	p=head;
    	while(p!=null){
    		System.out.println(p.val);
    		p=p.next;
    	}
        return head;
    }  
    public static void main(String[] args){
    	ListNode x1=new ListNode(1);
    	ListNode x2=new ListNode(2);
    	ListNode x3=new ListNode(3);
    	ListNode x4=new ListNode(4);
    	ListNode x5=new ListNode(5);
    	x1.next=x2;
    	x2.next=x3;
    	x3.next=x4;
    	x4.next=x5;
    	
    	Code61 code=new Code61();
    	code.rotateRight(x1, 5);
    }
}
